Threshold schemes could potentially allow connections to be terminated at the CDN with reduced privacy impact.

Focus on thresholdising multivariate-based signatures schemes.

Multivariate Quadratic Cryptography (MQ)

Is based on the assumed hardness of finding a solution (if exists) to a system of multivariate quadratic equations over a finite field. This is called the MQ problem.

It’s known to be NP-hard on average for an extensive range of parameters.

General Notation

$n$ is number of variables, $m$ is number of equations. $F_q$ is the finite field of prime order $q$.

Form

All coefficients are in $F_q$

Essentially the problem is that given a multivariate quadratic map, and a target in the co-domain, find an input in the domain that gives it.

Types

Pure-MV: random system

MQDSS SOFIA MUDFISH

Trapdoors

Oil and Vineger (OV-based)

C*-like

---

Trapdoor-based

Maps look random but in reality have a hidden structure that is only known to the signer. They are based on the Hash-and-Sign with Retries approach.

A public key is the function $P$ that is the trapdoor function. The secret key is the information about the trapdoor that allows the signer to invert it easily. A signature is some input $s$ where $P(s) = H(m || salt)$.

Unbalanced Oil and Vinegar

Trapdoor: linear subspace $O \subset \mathbb{F}^n_q$ (oil space) of dimension $m$ on which $P$ vanishes ( for every vector: $P(o)=0 \\ \forall o\in O$)

The signature is $P(s=(v+o))=H(msg||salt)$

• $o$ corresponds to the space where $P$ vanishes
• We construct $P$ such that we are assured this happens
• For every signature, we have a different $v$ and $o$

Signing

• Pick random $v\in \mathbb{F}_q^n$ (the vinegar)
• Solve for $o\in O$ (the oil), such that $P(v,o)=t$
• signature $s = o + v$ Signing is the hardest bit to thresholdise.

A Commitment Scheme can technically be built out of MQ, but will not be efficient.

@claucece